﻿// 103 最长上升子序列.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <algorithm>

using namespace std;
/*
http://oj.daimayuan.top/course/5/problem/135

给定一个长度为 n的数组 a1,a2,…,an
，问其中的最长上升子序列的长度。也就是说，我们要找到最大的 m以及数组 p1,p2,…,pm
，满足 1≤p1<p2<⋯<pm≤n并且 ap1<ap2<⋯<apm。

输入格式
第一行一个数字 n。

接下来一行 n个整数 a1,a2,…,an。

输出格式
一个数，表示答案。

样例输入
6
3 7 4 2 6 8

6
1 2 3 4 5 6

6
6 5 4 3 2 1

样例输出
4
数据规模
对于所有数据，保证 1≤n≤1000,1≤ai≤109。
*/

const int N = 1010;
int arr[N];
int dp[N];
int n;
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) { cin >> arr[i]; }
	arr[0] = -1;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1];
		for (int j = i - 1; j >= 0; j--) {
			if (arr[i] > arr[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
			ans = max(ans, dp[i]);
		}
	}

	cout << ans << endl;
	return 0;
}

 